import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test0511 {

}

class Solution {
	int[] x1= {1,0};
	int[] y1= {0,1};
	boolean[][] b;
	int r;
	int c;
	int[][] obstacleGrid1;
	List<List<Integer>> path;
public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
	
	 path=new ArrayList<List<Integer>>();
	r=obstacleGrid.length;
    c=obstacleGrid[0].length;
    b=new boolean[r][c];
    obstacleGrid1=obstacleGrid;
	if(r==0||obstacleGrid[r-1][c-1]==1||obstacleGrid[0][0]==1) {
		return path;
	}
	b[0][0]=true;
    path.add(Arrays.asList(0,0));
	boolean b=dfs(0,0);
    if(b==false){
        return new ArrayList<List<Integer>>();
    }
	return path;
}

boolean dfs(int i,int j) {
	if(i==r-1&&j==c-1) {
		return true;
	}
	for(int k=0;k<2;k++) {
		int x=i+x1[k];int y=j+y1[k];
		if(x<r&&y<c&&obstacleGrid1[x][y]!=1&&b[x][y]!=true) {
			b[x][y]=true;
			path.add(Arrays.asList(x,y));
			if(dfs(x,y))return true;
			b[x][y]=false;
			path.remove(path.size()-1);
		}
	}
	return false;
}
}

